The present invention relates generally to software defined networks, and more particularly, to layer 2 path tracing through context encoding in software defined networks.
Software-Defined Networking (SDN) allows network management much more flexible by decoupling the control plane where forwarding decisions are made from the data plane where forwarding actually happens. Network administrators can simply manage networks through abstractions of lower-level functionality. There can be one or more network controllers sitting in the control plane responsible for translating network administrators' abstracted policies into lower-level configurations that are subject to enact by switches. Although such abstraction hides the complexity underneath to network administrators, the ability for network administrators to verify whether switches' enaction agrees with their intended policies is a required feature in SDN troubleshooting.
The present invention focuses on a specific aspect of network troubleshooting in SDN, path tracing. Path tracing is the operation for determining the actual Layer 2 path taken by a given packet. Path tracing is important for network operators in carrying out performance optimization, e.g., comparing various routing options in load balancing, routing validation, e.g., ensuring that a routing algorithm performs correctly, and resource allocation e.g., identifying hot and cold spots in networks.
Currently, network operators rely on several approaches to determine the Layer 2 path of a packet, but to our best knowledge, all of them too much rely on the control plane, rather than determining the actual forwarding behavior in the data plane.
Referring to reference [1] below, ndb is a network debugger for SDN which emits postcards from every switch that the traced packet traverses. A postcard is a logging packet that contains information about the traced packet and the flow entry it matched. The network controller collects all postcards and reconstructs the packet path. The concern of that approach is the overhead of logging added to the control plane.
In Layer 3, hash-based IP traceback techniques, see reference [2] below, store packet digests on routers and use them to reconstruct the path of a packet. Extending such approach to Layer 2 comes with the expense of additional instrumentation on switches.    [1] Handigol, N., Heller, B., Jeyakumar, V., Mazi_eres, D., and McKeown, N. Where is the debugger for my software-de_ned network? In Proceedings of the First Workshop on Hot Topics in Software Defined Networks (New York, N.Y., USA, 2012), HotSDN '12, ACM, pp. 55 {60.    [2] Snoeren, A. C., Partridge, C., Sanchez, L. A., Jones, C. E., Tchakountio, F., Kent, S. T., and Strayer, W. T. Hash-based ip traceback. In Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (New York, N.Y., USA, 2001), SIGCOMM '01, ACM.
Accordingly, there is a need for a solution to implement an SDN Layer 2 path tracing utility.